package C032;

// 位图的实现
// Bitset是一种能以紧凑形式存储位的数据结构
// Bitset(int n) : 初始化n个位，所有位都是0
// void fix(int i) : 将下标i的位上的值更新为1
// void unfix(int i) : 将下标i的位上的值更新为0
// void flip() : 翻转所有位的值
// boolean all() : 是否所有位都是1
// boolean one() : 是否至少有一位是1
// int count() : 返回所有位中1的数量
// String toString() : 返回所有位的状态
public class Code02_DesignBitsetTest {
	public static void main(String[] args) {
		Bitset bitset = new Bitset(5);
		bitset.fix(3);
		bitset.flip();
		bitset.fix(2);
		System.out.println(bitset);

		// "Bitset","flip","unfix","all","fix","fix","unfix","all","count",
		Bitset bitset1 = new Bitset(2);
		bitset1.flip();
		bitset1.unfix(1);
	}

	static class Bitset {
		int[] bits;
		int size;
		int ones;
		int zeros;
		boolean reverse;

		public Bitset(int size) {
			bits = new int[(size + 31) / 32];
			this.size = size;
			ones = 0;
			zeros = size;
			reverse = false;
		}

		public void fix(int idx) {
			int index = idx / 32;
			int bit = idx % 32;
			if(!reverse) {
				if((bits[index] & (1 << bit)) == 0) {
					bits[index] |= (1 << bit);
					ones++;
					zeros--;
				}
			}else {
				// 0 即为 存在
				// 1 即为 不存在
				if((bits[index] & (1 << bit)) != 0) {
					bits[index] ^= (1 << bit);
					ones ++;
					zeros --;
				}

			}
		}

		public void unfix(int idx) {
			int index = idx / 32;
			int bit = idx % 32;
			if(!reverse) {
				if((bits[index] & (1 << bit)) != 0) {
					bits[index] &= ~(1 << bit);
					ones--;
					zeros++;
				}
			}else {
				// 0 为存在
				// 1`为存在
				if((bits[index] & (1 << bit)) == 0) {
					bits[index] |= (1 << bit);
					ones--;
					zeros++;
				}
			}
		}

		public void flip() {
			reverse = !reverse;
			ones = ones ^ zeros;
			zeros = ones ^ zeros;
			ones = ones ^ zeros;
		}

		public boolean all() {
			return ones == size;
		}

		public boolean one() {
			return ones > 0;
		}

		public int count(){
			return ones;
		}

		public String toString() {
			StringBuilder stringBuilder = new StringBuilder();
			for (int i = 0, number, bit; i < size;) {
				number = bits[i / 32];
				for (int j = 0; j < 32 && i < size; j++, i++) {
					bit = (number >>> j) & 1;
					bit = reverse ? (bit ^ 1) : bit;
					stringBuilder.append(bit);
				}
			}
			return stringBuilder.toString();
		}
	}

}
